package com.demo.java.OD351_400.OD379;

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【生日礼物(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146238366
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input1 = scanner.next();
        String input2 = scanner.next();
        String input3 = scanner.next();

        List<Integer> cakes = splitString(input1);  // 解析输入的蛋糕参数
        List<Integer> gifts = splitString(input2);  // 解析输入的礼物参数
        int total = Integer.parseInt(input3);

        cakes.sort(null);  // 对蛋糕参数进行排序

        int result = 0;
        for (int gift : gifts) {
            if (total <= gift) {
                continue;  // 如果礼物参数大于等于总数，则跳过当前礼物
            }
            int i = searchLastIndex(cakes, total - gift);  // 在蛋糕参数中查找目标值
            result += (i >= 0) ? (i + 1) : (-i - 1);  // 根据查找结果更新结果值
        }

        System.out.println(result);
    }

    private static List<Integer> splitString(String paramsStr) {
        List<Integer> p = new ArrayList<>();
        int start = 0;
        int end;
        while ((end = paramsStr.indexOf(",", start)) != -1) {
            p.add(Integer.parseInt(paramsStr.substring(start, end)));  // 解析逗号分隔的参数并添加到列表中
            start = end + 1;
        }
        p.add(Integer.parseInt(paramsStr.substring(start)));  // 添加最后一个参数到列表中
        return p;
    }

    private static int searchLastIndex(List<Integer> nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums.get(mid) > target) {
                right = mid - 1;  // 目标值在左半部分，缩小右边界
            } else if (nums.get(mid) < target) {
                left = mid + 1;  // 目标值在右半部分，缩小左边界
            } else {
                if (mid == nums.size() - 1 || nums.get(mid) != nums.get(mid + 1)) {
                    return mid;  // 找到目标值的最后一个索引
                } else {
                    left = mid + 1;  // 目标值有重复，继续向右查找
                }
            }
        }
        return -left - 1;  // 没有找到目标值，返回应插入的位置的负数索引
    }
}